/**
 * Created with IDEA
 * author:ju bai
 * Date:2021/5/21
 * Time:15:28
 **/
public class Main2 {
    /**
     * 每日一题-年终奖
     * 求小东可以获得的最大价值
     * 子问题：小东走到某个格子的最大价值
     * F(i,j)=max(F(i-1,j),F(i,j-1))+board[i][j];
     * 上相邻和左相邻比较，再往下往右走
     *
     * @param board
     * @return
     */
    public int getMost(int[][] board) {
        int row = board.length;
        int col = board[0].length;
        //第一行
        for (int i = 1; i < col; i++) {
            board[0][i] += board[0][i - 1];
        }
        //第一列
        for (int i = 1; i < row; i++) {
            board[i][0] += board[i - 1][0];
        }
        //剩余位置
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                board[i][j] += Math.max(board[i - 1][j], board[i][j - 1]);
            }
        }
        return board[row - 1][col - 1];
    }
}
